package leetcode.code0368;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

//执行用时：44 ms, 在所有 Java 提交中击败了5.09%的用户
//
//内存消耗：41.5 MB, 在所有 Java 提交中击败了13.40%的用户
//
//通过测试用例：49 / 49
public class Solution6 implements IDebug {

	class Node {
		Node next;
		int seq;
		int val;

		public Node(int seq, int val) {
			this.seq = seq;
			this.val = val;
		}
	}

	public List<Integer> largestDivisibleSubset(int[] nums) {
		Arrays.sort(nums);
		Node[] heads = new Node[nums.length];
		Node first = new Node(1, nums[0]);
		int p = 0;
		heads[p++] = first;
		Node max = first;
		for (int i = 1; i < nums.length; i++) {
			int cur = nums[i];
			Node node = new Node(1, cur);
			for (int j = p - 1; j >= 0; j--) {
				Node head = heads[j];
				if (cur % head.val == 0 && head.seq >= node.seq) {
					node.seq = head.seq + 1;
					node.next = head;
					if (node.seq > max.seq) {
						max = node;
					}
				}
			}
			heads[p++] = node;
		}
		List<Integer> ans = new ArrayList<>();
		while (max != null) {
			ans.add(max.val);
			max = max.next;
		}
		return ans;
	}

	@Override
	public void debug1() {
		List<Integer> ans = HelpDebug.str2intlist("[9,18,90,180,360,720]");
		HelpDebug.compare(ans, this.largestDivisibleSubset(HelpDebug.str2array3("[5,9,18,54,108,540,90,180,360,720]")));

	}

	@Override
	public void debug2() {
		List<Integer> ans = HelpDebug.str2intlist("[4,8,16]");
		HelpDebug.compare(ans, this.largestDivisibleSubset(HelpDebug.str2array3("[3,4,16,8]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub
		List<Integer> ans = HelpDebug.str2intlist("[2,4,8]");
		HelpDebug.compare(ans, this.largestDivisibleSubset(HelpDebug.str2array3("[2,3,4,8]")));

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution6 so = new Solution6();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
